package com.dhu.graph.utils;

import java.awt.*;
import java.util.Arrays;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-09
 * @ Description：元素存储在keys中，元素在keys中的索引在pq中代替元素上浮下沉
 * @ Modified By：
 * @ Version:
 */
public class IndexMinPQ<E extends Comparable<E>> {

    private int[] pq; // 存储索引的优先队列
    private int[] qp; // 反向索引，根据索引查询索引在pq中的位置，pq[i] = j, qp[j] = i;
    private E [] keys;  // 存储正真的元素
    private int capacity;   // 元素的个数
    private int N;

    public IndexMinPQ(){
        this(16);
    }
    public IndexMinPQ(int size){
        this.pq = new int[size + 1];
        this.qp = new int[size + 1];
        keys = (E[])new Comparable[size + 1];
        this.capacity = size + 1;
        for (int i = 0; i < size + 1; i ++){
            pq[i] = -1;
            qp[i] = -1;
        }
    }
    synchronized public void insert(int index, E key){
        if (index < 0) return;
        if (index > capacity)
            resize(index << 2);
        keys[index] = key;
        pq[++N] = index;
        qp[index] = N;
        swim(N);
        if (capacity - N < 2) resize(capacity << 2);
    }

    /**
     * 删除最小元素
     * @return
     */
    synchronized public int delMin(){
        int ret = qp[1];
        exch(1, N);
        pq[N --] = -1;
        sink(1);
        return ret;
    }
    public boolean isEmpty(){
        return N == 0;
    }
    public boolean contains(int index){
        return qp[index] >= 0 && index < capacity;
    }
    private void resize(int newCap){
        this.keys = Arrays.copyOf(keys, newCap);
        this.pq = Arrays.copyOf(pq, newCap);
        this.qp = Arrays.copyOf(qp, newCap);
        this.capacity = newCap;
        for (int i = N + 1; i < newCap; i++){
            pq[i] = -1;
            qp[i] = -1;
        }

    }
    synchronized public void change(int index, E key){
        if (pq[index] == -1 || index <= 0 || index >= capacity)
            throw new RuntimeException("No Such Element");
        keys[index] = key;
        swim(qp[index]);
        sink(qp[index]);
    }

    /**
     * 在pq中交换pq[i] 和pq[j]
     * @param i
     * @param j
     */
    private void exch(int i, int j){
        qp[pq[i]] = j;
        qp[pq[j]] = i;
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /**
     * 索引为pq[i]的元素是否小于索引为pq[j]
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j){
        return keys[pq[i]].compareTo(keys[pq[j]]) <= 0;
    }

    /**
     * pq中的索引上浮
     * @param i
     */
    private void swim(int i){
        while (i > 1 && less(pq[i],pq[i / 2])){
            exch(i, i / 2);
        }
    }

    /**
     * pq中的索引下沉
     * @param i
     */
   private void sink(int i){
        while (2 * i <= N){
            int j = 2 * i;
            if (less(j + 1, j)) j++;    // 2 *  i是左边的元素，要保证父节点比两个子节点小，下沉时要与两个子节点中较小的比较
            if (less(i, j)) break;
            else exch(i, j);
            i = j;
        }
   }

}
